package 力扣日常刷题.木22一月.第13天0121;

import 力扣日常刷题.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 帅小伙
 * @date 2022/1/21
 * @description
 */
public class Demo40动态规划中等打家劫舍3 {

    // f 选择    g没有选择
    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();


    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0));
    }

    void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        dfs(node.right);

        f.put(node, node.val + g.getOrDefault(node.right, 0) + g.getOrDefault(node.left, 0));
        // 选左不选左  选右不选右
        g.put(node, Math.max(f.getOrDefault(node.left, 0),
                g.getOrDefault(node.left, 0)) +
                Math.max(f.getOrDefault(node.right, 0),
                        g.getOrDefault(node.right, 0)));
    }
}
